package com.dubious.interview.euler;

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.dubious.interview.euler.prime.FilePrimeIterator;


public class Problem111 {

    /**
     * Considering 4-digit primes containing repeated digits it is clear that they cannot all be 
     * the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 
     * 4-digit primes containing three ones:
     * 
     * 1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111
     * 
     * We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit 
     * prime where d is the repeated digit, N(n, d) represents the number of such primes, and 
     * S(n, d) represents the sum of these primes.
     * 
     * For d = 0 to 9, the sum of all S(4, d) is 273700.
     * 
     * Find the sum of all S(10, d).
     */
    public static long run(int n) throws IOException
    {
        //List<Long> primes = Utilities.sieveOfEratosthenes((long)Math.pow(10, n));
        
        // Have 10 items tracking the set of primes which are part of N(n, 1), N(n, 2), etc...
        List<RepeatedDigits> allRepeatedDigits = new ArrayList<RepeatedDigits>(10);
        for(int i = 0; i < 10; i++)
        {
            allRepeatedDigits.add(new RepeatedDigits());
        }
        
        long minimum = (long)Math.pow(10, n - 1);
        for(Long prime : new FilePrimeIterator((long)Math.pow(10, n)))
        {
            // TODO: Skip primes that do not contain expected number of digits
            if(prime - minimum < 0)
            {
                continue;
            }
            
            int[] digitCounts = new int[10];
            for(int digit : Utilities.extractDigits(prime))
            {
                digitCounts[digit]++;
            }
                
            for(int i = 0; i < 10; i++)
            {   
                // finished all digits, deal with the final sequence
                if(digitCounts[i] == allRepeatedDigits.get(i).numRepeatedDigits)
                {
                    // num in sequence equal to greatest found, add it to the set
                    allRepeatedDigits.get(i).primes.add(prime);
                } else if(digitCounts[i] > allRepeatedDigits.get(i).numRepeatedDigits)
                {
                    // num in sequence greatest found thus far, make a new set with it
                    RepeatedDigits repeatedDigits = new RepeatedDigits();
                    repeatedDigits.numRepeatedDigits = digitCounts[i];
                    repeatedDigits.primes.add(prime);
                    allRepeatedDigits.set(i, repeatedDigits);
                }
            }
        }
        
        // gather all of the digits into a single set and sum them
        long sum = 0;
        for(RepeatedDigits repeatedDigits : allRepeatedDigits)
        {
            for(Long prime : repeatedDigits.primes)
            {
                sum += prime;
            }
        }
        
        return sum;
    }
    
    private static class RepeatedDigits
    {
        private int numRepeatedDigits = 0;
        private List<Long> primes = new LinkedList<Long>(); 
    }
}
